package data_structures_and_algorithms.stack_queue.stack;

import java.security.PrivateKey;
import java.util.*;

/**
 * @ClassName Code_0020_isValidParentheses
 * @Description: TODO
 * @Author: yongliang.ma
 * @Create_time:2022/10/28 13:51
 */
public class Code_0020_isValidParentheses {

    // 使用栈得特性：先进先出特点
    public boolean isValid(String s) {
        if ((s.length() & 1) == 1){
            return false;
        }
        Map<Character, Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        Set<Character> set = new HashSet<>();
        set.add('(');
        set.add('[');
        set.add('{');
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i))){
                deque.addFirst(s.charAt(i));
                continue;
            }else {
                char expect = map.getOrDefault(s.charAt(i), null);
                if (!deque.isEmpty() && expect == deque.getFirst()){
                    deque.removeFirst();
                }else {
                    return false;
                }
            }
        }
        return deque.isEmpty();
    }




}
